package com.wfm.leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class PNine94腐烂的橘子{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    public int orangesRotting(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int bad = 0;
        int cnt=0;
        int res=0;
        Queue<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j]==2){
                    queue.offer(new int[]{i,j});
                    bad++;
                }
                if(grid[i][j]!=0){
                    cnt++;
                }
            }
        }
        if(cnt-bad==0) return 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();

                int[][] direct = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
                for(int[] d:direct){
                    int ni = cur[0]+d[0];
                    int nj = cur[1]+d[1];
                    if(ni>=0&&ni<m&&nj>=0&&nj<n&&grid[ni][nj]==1){
                        queue.offer(new int[]{ni,nj});
                        grid[ni][nj]=2;
                        bad++;
                    }
                }
            }
            res++;
        }
        return bad==cnt?res-1:-1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new PNine94腐烂的橘子().new Solution();
//        int[][] ints = {{2,1,1},{1,1,0},{0,1,1}};
//        int[][] ints = {{2,1,1},{0,1,1},{1,0,1}};
        int[][] ints = {{0}};
        int i = solution.orangesRotting(ints);
        System.out.println(i);
    }
}